//题目:
// 小朋友A在和ta的小伙伴们玩传信息游戏，游戏规则如下：
// 有n名玩家，所有玩家编号分别为0 ～ n-1，其中小朋友A的编号为 0
// 每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如A可以向B传信息，但B不能向A传信息）。
// 每轮信息必须需要传递给另一个人，且信息可重复经过同一个人
// 给定总玩家数n，以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。
// 返回信息从小A(编号0)经过k轮传递到编号为n-1的小伙伴处的方案数；若不能到达，返回0。
#include<iostream>
#include<queue>
#include<unordered_map>

using namespace std;
//代码:
class Solution 
{
public:
    int numWays(int n, vector<vector<int>>& relation, int k) 
    {
        //1.要能实现:通过key找到value的功能，即哈希表
        unordered_multimap<int,int> multi_hash;
        //2.给哈希表插入数据
        for(int i=0;i<relation.size();i++)
            multi_hash.insert(make_pair(relation[i][0],relation[i][1]));
        //3.元素入队列一次，就相当于信息传递一次
        queue<pair<int,int>> q;
        //将0所能传递的元素值全部插入q中
        for(const auto& pir:multi_hash)
            if(pir.first==0)
                q.push(make_pair(pir.first,pir.second));
        while(!q.empty() && k>1)
        {
            k--;
            //同层元素全部出队列，同时，将其各自的子元素入队列
            int size=q.size();
            for(int i=0;i<size;i++)
            {
                pair<int,int> tmp=q.front();
                q.pop();//出队列
                //将tmp.first所能传递的元素值全部插入q中
                for(const auto& pir:multi_hash)
                    if(tmp.second==pir.first)
                        q.push(make_pair(pir.first,pir.second));
            }
        }
        //4.计算q中剩余的元素中second==n-1的元素个数
        int ret=0;
        while(!q.empty())
        {
            pair<int,int> pir=q.front();
            q.pop();
            if(pir.second==n-1)ret++;
        }
        return ret;
    }
};